package com.cjm.algorithm.tree;

import com.cjm.algorithm.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Ti113 {
    public static void main(String[] args) {

    }

    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        // 叶子点
        res.clear();
        if (root == null) {
            return res;
        }
        // 和 = target
        findListTarget113(root, targetSum, new LinkedList<>(), 0);
        return res;
    }

    private void findListTarget113(TreeNode root, int targetSum, LinkedList<Integer> hh, int curvalue) {
        curvalue += root.val;
        hh.addLast(root.val);
        if (curvalue == targetSum && root.left == null && root.right == null) {
            res.add(new ArrayList<>(hh));
            hh.pollLast();
            return;
        }
        if (root.left != null) {
            findListTarget113(root.left, targetSum, hh, curvalue);
        }
        if (root.right != null) {
            findListTarget113(root.right, targetSum, hh, curvalue);
        }
        hh.pollLast();
    }
}
